package problem.year2021.march;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 * 整数除法仅保留整数部分。
 */
public class March11 {
    public int calculate(String s) {
        // 去掉无用的空格
        s = s.replaceAll(" ", "");
        int len = s.length();
        System.out.println("len = " + len);
        char[] chars = s.toCharArray();
        Deque<Integer> number = new ArrayDeque<>();
        Deque<Character> arith = new ArrayDeque<>();
        int temp = 0;
        out2:
        for (int i = 0; i < len; ++i) {
            out:
            switch (chars[i]) {
                case '+':
                    number.addLast(temp);
                    temp = 0;
                    arith.addLast('+');
                    break;
                case '-':
                    number.addLast(temp);
                    temp = 0;
                    arith.addLast('-');
                    break;
                case '*':
                    // 把上一个元素入队列
                    number.addLast(temp);
                    temp = 0;
                    ++i;
                    for (int j = i; j < len; ++j) {
                        if (chars[j] <= '9' && chars[j] >= '0') {
                            temp = temp * 10 + chars[j] - '0';
                        } else {
                            i = j -1;
                            temp = number.pollLast() * temp;
                            break out;
                        }
                    }
                    temp = number.pollLast() * temp;
                    break out2;
                case '/':
                    // 把上一个元素入队列
                    number.addLast(temp);
                    temp = 0;
                    ++i;
                    for (int j = i; j < len; ++j) {
                        if (chars[j] <= '9' && chars[j] >= '0') {
                            temp = temp * 10 + chars[j] - '0';
                        } else {
                            i = j -1;
                            temp = number.pollLast() / temp;
                            break out;
                        }
                    }
                    temp = number.pollLast() / temp;
                    break out2;
                default:
                    temp = temp * 10 + chars[i] - '0';
            }
        }
        number.addLast(temp);
        if (arith.isEmpty()) return number.pop();
        int sum = number.pollFirst();
        while (!arith.isEmpty()){
            if (arith.pollFirst() == '-'){
                sum -= number.pollFirst();
            } else sum += number.pollFirst();
        }
        return sum;
    }

    /**
     * 示例 1：
     * 输入：s = "3+2*2"
     * 输出：7
     * 示例 2：
     * 输入：s = " 3/2 "
     * 输出：1
     * 示例 3：
     * 输入：s = " 3+5 / 2 "
     * 输出：5
     */
    public static void main(String[] args) {
        System.out.println(new March11().calculate("1*2*3*4*5*6*7*8*9*10"));
        System.out.println(1*2*3*4*5*6*7*8*9*10);
    }
    class Solution {
        public int calculate(String s) {
            Deque<Integer> stack = new LinkedList<Integer>();
            char preSign = '+';
            int num = 0;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                if (Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                }
                if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                    switch (preSign) {
                        case '+':
                            stack.push(num);
                            break;
                        case '-':
                            stack.push(-num);
                            break;
                        case '*':
                            stack.push(stack.pop() * num);
                            break;
                        default:
                            stack.push(stack.pop() / num);
                    }
                    preSign = s.charAt(i);
                    num = 0;
                }
            }
            int ans = 0;
            while (!stack.isEmpty()) {
                ans += stack.pop();
            }
            return ans;
        }
    }
}
